package com.cwj.lab4.查找.查找树;

import java.util.TreeMap;

/**
 * 二叉查找树
 * */
public class BSTree<T extends Comparable<T>, E> {
    //树节点
    public static class Node<T, E> {
        T key;//键
        E val;//数据域
        Node<T, E> lef;
        Node<T, E> rig;

        public Node(T key, E val, Node<T, E> lef, Node<T, E> rig) {
            this.key = key;
            this.val = val;
            this.lef = lef;
            this.rig = rig;
        }
    }

//树的根节点
    private Node<T, E> root;
//    有效元素数目
    private int Sum;

    public BSTree() {
        root = null;
        Sum = 0;
    }

    public BSTree(Node<T, E> root) {
        this.root = root;
    }
/**
 * 添加元素
 * */
    public void add(T key, E data) {
        if (this.root == null) {
            root = new Node<T, E>(key, data, null, null);
            Sum += 1;
            return;
        }
        Node<T, E> flag = root;
        while (true) {
            if (key.compareTo((T) flag.key) < 0) {
                if (flag.lef == null) {
                    flag.lef = new Node<T, E>(key, data, null, null);
                    break;
                }
                flag = flag.lef;
            } else {
                if (flag.rig == null) {
                    flag.rig = new Node<T, E>(key, data, null, null);
                    break;
                }
                flag = flag.rig;
            }
        }
        Sum += 1;
    }
/**
 * 删除元素
 * */
    private E del(T key) {
        if (this.root == null) {
            return null;
        }
        Node<T, E> pre = null;
        Node<T, E> now = this.root;
        while (now != null) {
            int sig = key.compareTo(now.key);
            if (sig < 0) {
                pre = now;
                now = now.lef;
            } else if (sig == 0) {
                break;
            } else {
                pre = now;
                now = now.rig;
            }
        }
        E data = null;
        if (now == null) {
            return null;
        } else {
            data = now.val;
            this.Sum-=1;
        }
        //删除节点
        Node<T, E> flag = now;
        if (now.lef != null && now.rig != null) {
            Node<T, E> nn = now.lef;
            Node<T, E> preNN = now;
            while (nn.rig != null) {
                preNN = nn;
                nn = nn.rig;
            }
            now.val = nn.val;
            now.key = nn.key;
            if (preNN != now) {
                preNN.rig = nn.lef;
            } else {
                preNN.lef = nn.lef;
            }
        } else if (now.lef != null) {
            now = now.lef;
        } else {
            now = now.rig;
        }
        //将点挂上去
        if (pre == null) {
            this.root = now;
        } else if (pre.lef == flag) {
            pre.lef = now;
        } else {
            pre.rig = now;
        }
        return data;
    }
/**
 * 查找函数
 * */
    public E find(T key) {
        Node<T, E> nn = this.find_2(key);
        return nn != null ? nn.val : null;
    }

    private Node<T, E> find_2(T key) {
        Node<T, E> flag = this.root;
        while (flag != null) {
            if (flag.key.compareTo(key) < 0) {
                flag = flag.rig;
            } else if (flag.key.compareTo(key) == 0) {
                return flag;
            } else {
                flag = flag.lef;
            }
        }
        return null;
    }
/**
 * 重写toString
 * 为了让输出的字符串为树的中序遍历序列
 * */
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        this.toString(this.root, sb);
        return sb.toString();
    }

    public void toString(Node<T, E> head, StringBuffer sb) {
        if (head == null) return;
        toString(head.lef, sb);
        sb.append(head.key).append(" ");
        toString(head.rig, sb);
    }
/**
 * 获得元素总数
 * */
    public int getSum() {
        return Sum;
    }
//测试函数
    public static void main(String[] args) {
        BSTree<Integer, Integer> bst = new BSTree<>();
        TreeMap<Integer, Integer> tree = new TreeMap<>();
        int size = 20,NUM=15;
        for (int i = 0; i < size; i++) {
            bst.add((int) (Math.random() * 10 ), (int) (Math.random() * 30));
        }
        System.out.println(bst.getClass().getSimpleName());
        System.out.println(bst);
        choose(bst,NUM);

    }

    static void choose(BSTree<Integer, Integer> bst, int num) {
        for (int i = 0; i < num; i++) {
            int ind = 1;//(int) (Math.random() * 2);
            int key = (int) (Math.random() * 10);
            int data = (int) (Math.random() * 100);
            switch (ind) {
                case 0:
                    System.out.print("add(key=" + key + ",data=" + data + ")一次:");
                    bst.add(key, data);
                    System.out.print(bst);
                    break;
                case 1:
                    System.out.print("del(key=" + key + "):");
                    System.out.println(bst.del(key));
                    System.out.print(bst);
                    break;
            }
            System.out.println();
        }
    }
}
